import java.util.Arrays;

public class LeetCode1833 {
    public static void main(String[] args) {
        int[] costs = {1, 3, 2, 4, 1};
        int coins = 7;

        System.out.println(maxIceCream(costs, coins));
    }

    public static int maxIceCream(int[] costs, int coins) {
        int n = costs.length, i = 0, x = 0, res = 100000;
        long d = 0;
        for (; i < n; ++i) {
            d += costs[i];
            if (costs[i] > x) x = costs[i];
            if (costs[i] < res) res = costs[i];
        }
        if (coins >= d) return n;
        if (x == res) return coins / res;
        byte[] freq = new byte[x + 1];
        for (int cost : costs) ++freq[cost];
        for (x = i = res, res = 0; i <= coins; x = ++i) {
            x *= n = freq[i];
            if (x > coins) return res += coins / i;
            res += n;
            coins -= x;
        }
        return res;
    }

    public static int maxIceCreamGreedy(int[] costs, int coins) {
        int res = 0;
        Arrays.sort(costs);
        int n = costs.length;
        for (int i = 0; i < n; i++) {
            if (coins - costs[i] >= 0) {
                coins -= costs[i];
                res++;
            } else {
                break;
            }
        }
        return res;
    }
}
